This invention relates to the generation of smooth lines or edges of images in raster-scan type displays, and more particularly to line generating apparatus for displaying smooth lines with intensity and color modulated picture elements (pixels). As used herein, the word "line" shall generally be deemed to include and cover edges of characters or other images.
To reconstruct a line in raster format, digital differential analyzer (DDA) may be used. For each incremental step of the DDA, say on the X axis, Y-position information will be generated for every pixel in the line. This is true, of course, for lines closer to the X axis (less than 45 degrees from horizontal). For lines closer to vertical (Y axis), the DDA will generate X-position information for steps along the Y axis. Accordingly, in the former case the so-called large axis would be the X axis and in the latter case the large axis would be the Y axis, and in each case the so-called small axis would be the axis perpendicular thereto. Thus, the DDA steps along the large axis, generating small axis position information.
Due to the fixed location of the raster pixels, the equivalent line usually has a staircase structure or is jagged. If the DDA is allowed to operate at a higher resolution than the raster screen resolution, the distance between the true or theoretical line and the individual pixel position (a function of the small axis distance) can be resolved and utilized in terms of modulating pixel intensity to create the appearance of a smooth line.
This technique has been successfully implemented in so-called purely software arrangements involving complex and very precise algorithms, and in hardware arrangements as may be represented, for example, by the disclosure in Japanese Patent Application No. 2626/79, filed on Jan. 12, 1979 to Daini Seikosha (Disclosure No. 95986/80, July 21, 1980; inventor Masayuki Matsumoto). A basic objection of the purely software arrangements is the relative slowness with which the lines are recreated accurately in display (i.e. graphics drawing speed), which is a principal result of the sequential nature of internal operation of such an arrangement.
Known hardware systems, while generally being able to substantially improve upon the speed of operation, nevertheless significantly suffer in terms of the actual displayed image by virtue of inadequate intensity (and color) modulation regarding the full compliment of pixels relevantly associated by position to the true or theoretical line intended to be recreated. Moreover, such systems tend to produce images in which readily apparent changes in line thickness occur as a function of the slope of the line. That is, lines other than vertical (Y axis) or horizontal (X axis) will varyingly (with slope) appear thinner, with lines having a 45 degree slope orientation appearing thinnest of all.
Additionally, these systems do not resolve the line end points to fractional pixel precision, and the lines must begin and end centered on a pixel position. Thus, although an advance may be provided with respect to line smoothing per se, none is provided with regard to precise line positioning. This effect is particularly undesirable in the case of approximately smooth curves comprised of many short vectors or line segments.
Even if such systems did resolve the end points to fractional pixel accuracy, there would still be needed special end point treatment to eliminate or prevent the appearance of angular slicing of the ends of the lines. This angular slicing effect stems from terminating the lines horizontally or vertically even when the lines are oriented other than vertically or horizontally.
In the arrangement depicted in the above-mentioned patent application, as example, intensity information may be said to be generated for two pixels on the small axis (e.g. Y axis) for each step along the large axis (X axis), i.e. the pixel on the line (or closest to it) and the adjacent pixel next closest to the line, with the total (fully-on) intensity of a single pixel being apportioned between them. Such line coverage is insufficiently selective to provide a highly accurate representation of the true line, particularly in view of those situations where all relevant pixels in the small axis for a given large axis increment would include not only the pixel on the line itself but the adjacent pixels on each side of the line. Moreover, this previously disclosed system does not solve the problem of varying line thickness with slope. It is thus deemed incapable of suggesting an efficient and high speed approach for full and consistent line coverage, i.e. providing small axis position information with regard to each pixel of a 3 (or more)-pixel array encompassing the line for a step along the large axis, and slope independence.
Reconstruction of a near-perfect anti-aliased or smooth image requires knowledge of every line crossing a given pixel before determining its intensity (or indeed its color in polychromatic systems), and utilization of this information to achieve an appropriate balance between the intensity values and/or colors associated to respective lines. A system attempting to carry this out would, however, be unacceptably slow.
Previous systems have either ignored the so-called old pixel value (e.g. the value already stored in the frame buffer system for a first line to be drawn), or used it in a so-called maximum value operation, with alpha (in its simplest form the fractional coverage of a pixel by the line to be drawn) times the line intensity. In the latter case, which is monochrome only, the effect is to write the new pixel value only if it is larger than the old value. In either case, the average errors are greater than say for proportional weighting when compared to the above-mentioned ideal case.
The above drawbacks are overcome according to the present invention, wherein a high speed system is provided for generating smooth lines to n bits (typically up to 6) of fractional pixel accuracy, both as to the line mid-section and its end points, and which provides special end points treatment which assures a true representation of the line, properly positioned, in display. The small axis distance information and slope information are utilized to assign alpha values (e.g. gray scale or intensity values in a monochrome system) to a set of pixels (at least 3) in an array providing a highly representative cross-section of the theoretical line for the incremental portions (large axis) of a DDA with consistency of line thickness regardless of line slope. Successive arrays of relevant pixels are sequentially treated efficiently in a zig-zag coverage of the line in conjunction with the special end points treatment. The small axis positional information for each array of pixels is generated within a single clock cycle. The alpha values generated are utilized, when appropriate, to provide proportional weighting between old pixel values and the desired line color, with alpha being the proportionality constant.
In a system according to the invention, sequencing of the pixels is such as to require only X and Y increment/decrement commands along with alpha values to be supplied to the frame buffer system. Since smoothing is accomplished during the building of the raster image, no after-filtering is required. Moreover, an operative mode of selective erase can be readily effected.